1. Field of the Invention
The invention generally relates to data transformation apparatus and methods, and in particular to the computation of Givens rotations.
2. Description of the Related Art
Givens rotations are widely used in numerical linear algebra and find many application in data communications systems. For instance, in spread spectrum systems such as wireless communications systems, the unitary Givens rotation is commonly used in adaptive filtering, equalization, and fast factorization algorithms.
Given the vectors xp,xq εCn with xp (1)≠0, a Givens rotation is a 2-by-2 unitary matrixQεC2×2such that[xpxq]Q=[x′px′q]where x′q(1)=0, i.e. the first element of the second column shall be made zero. Numerically stable solutions are given by
                    Q        =                                            [                                                                    α                                                                              -                      β                                                                                                                                  β                      *                                                                            α                                                              ]                        ⁢                                                  ⁢            α                    =                                                    1                                                      1                    +                                                                                          γ                                                                    2                                                                                  ⁢                                                          ⁢              β                        =                                          γ                ⁢                                                                  ⁢                α                ⁢                                                                  ⁢                γ                            =                                                                                                                                            x                          _                                                q                                            ⁡                                              (                        1                        )                                                                                                                                      x                          _                                                p                                            ⁡                                              (                        1                        )                                                                              ⁢                                                                          ⁢                  if                  ⁢                                                                          ⁢                                                                                                                                                                x                            _                                                    q                                                ⁡                                                  (                          1                          )                                                                                                            2                                                  <                                                                                                                                                  x                          _                                                p                                            ⁡                                              (                        1                        )                                                                                                  2                                                                                    and                          Q        =                                            [                                                                                          β                      *                                                                                                  -                      α                                                                                                            α                                                        β                                                              ]                        ⁢                                                  ⁢            α                    =                                                    1                                                      1                    +                                                                                          γ                                                                    2                                                                                  ⁢                                                          ⁢              β                        =                                          γ                ⁢                                                                  ⁢                α                ⁢                                                                  ⁢                γ                            =                                                                                                                                            x                          _                                                p                                            ⁡                                              (                        1                        )                                                                                                                                      x                          _                                                q                                            ⁡                                              (                        1                        )                                                                              ⁢                                                                          ⁢                  if                  ⁢                                                                          ⁢                                                                                                                                                                x                            _                                                    p                                                ⁡                                                  (                          1                          )                                                                                                            2                                                  ≤                                                                                                                                                                                x                            _                                                    q                                                ⁡                                                  (                          1                          )                                                                                                            2                                    .                                                                        
These are two types of Givens rotations, and as apparent therefrom, computing a Givens rotation requires in each case the computation of square root functions when determining the value of α. In the above example, computation of
      f    ⁡          (      ξ      )        =      1                  1        +        ξ            for ξ=|γ|2≦1 is required, in order to compute the value of α. This computation is cumbersome with respect to the hardware implementation since it involves both square root computation and inversion. In the following, the term square root function denotes any function such as function f shown above, that contains at least one square root, irrespective of whether there are other functional terms included such as that of an inversion.
One way of performing the square root function computation would be to provide a look-up table where for each possible value of ξ=|γ|2≦1, the corresponding value of the square root function is stored. However, in order to have a sufficiently high resolution with no sampling noise, the look-up table would be required to be of an inappropriately large size. Moreover, the provision of such look-up table would inadequately increase the manufacturing costs of such circuits.
An alternative would be to apply a polynomial approximation based on the respective binomial series:
                              1                                    1              +              ξ                                      =                  1          -                                    1              2                        ⁢            ξ                    +                                    3              8                        ⁢                          ξ              2                                -                                    5              16                        ⁢                          ξ              3                                +                                    35              128                        ⁢                          ξ              4                                -                                    63              256                        ⁢                          ξ              5                                +                                    231              1024                        ⁢                          ξ              6                                -          …                                        =                              ∑                          i              =              0                        ∞                    ⁢                                    c              i                        ⁢                          ξ              i                                          where ξ=|γ|2≦1.
Again, in order to compute the square root function with sufficient accuracy, the computational overhead would be inappropriately large. To have for each input value a sufficiently accurate functional value, it would be necessary to compute for each input value a high degree polynomial using the following polynomial coefficients:
c0+1.000000000000000000c1−0.500000000000000000c2+0.375000000000000000c3−0.312500000000000000c4+0.273437500000000000c5−0.246093750000000000c6+0.225585937500000000c7−0.209472656250000000c8+0.196380615234375000c9−0.185470581054687500c10+0.176197052001953125. . .. . .
Thus, this approach is numerically extensive since it involves a high number of floating point operations.
In order to avoid the need for square root computation, the so called fast Givens rotation may be applied which in addition reduces the required number of multiplications. However, a numerically stable version of the fast Givens rotation involves an increased amount of control overhead and an increased amount of divisions with respect to the standard Givens rotation, which makes its application less attractive for fixed point implementations.